Public Key Infrastructure (PKI) systems were developed to ensure communications privacy, and to protect sensitive data. Each party in a PKI system has two cryptographic keys: a public key and a private key. A party's public key is available to any other party. A party's private key is never revealed to any other user. PKI systems are discussed in detail in “Secure Electronic Commerce,” by Warwick Ford and Michael Baum, Prentice-Hall, ISBN 0-13-476342-4, which is hereby incorporated by reference in its entirety for its useful background information.
A serious problem encountered with PKI systems occurs when the need or desire exists to change a party's access privileges such as by modifying or removing the party's private key. This problem can be illustrated within the context of cryptographic file systems. Cryptographic file system may be used to control access to certain files on a computer system that is accessible by several individuals. The files to be controlled may be referred to as encrypted files. Once a party has had access to a particular set of encrypted files, there are several prior art approaches, none of which is convenient, for securely removing that access. These prior art approaches include: 1) changing the key-pair for the cryptographic file-set, 2) changing the symmetric encryption key for new writes, and 3) re-encrypting the entire file-set for which access rights have changed. Each of these approaches has drawbacks. Simply changing the key-pair that encrypts the symmetric file encryption key is not secure because no means exists for verifying that the party did not cache the symmetric file encryption key, which would allow access not only to previously stored information, but new information as well. Changing the symmetric encryption keys that are used for newly stored information provides some protection, but a party can still access all of the previously stored information in the cryptographic file-set. This solution has the additional disadvantage that there may eventually be many encryption keys needed to read a single file, which makes the system overly complex. The most secure solution is to re-encrypt the entire cryptographic file system when a party's access to the file-set is removed. While the most secure, this method is also very costly, especially if access rights change frequently. These and other access control problems are solved with a disclosed improved Secure Key Replacement Protocol (SKRP).